package Union_Set;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

//map实现并查集
public class Union_Set {

    public static  class Node<V>{
        V value;
        public  Node(V v){
                value=v;
        }
    }

    public static class UnionSet<V>{
        public HashMap<V,Node<V>> nodes;
        public HashMap<Node<V>,Node<V>> parents;
        public HashMap<Node<V>,Integer> sizeMap;


        public UnionSet(List<V> values){
            nodes=new HashMap<>();
            parents=new HashMap<>();
            sizeMap=new HashMap<>();
            for (V cur : values) {
                Node<V> node=new Node(cur);
                nodes.put(cur,node);
                parents.put(node,node);
                sizeMap.put(node,1);
            }
        }

        public Node<V> findFather(Node<V> cur){
            Stack<Node<V>> path=new Stack<>();
            while(cur!=parents.get(cur)){
                path.push(cur);
                cur=parents.get(cur);
            }
            //扁平化
            while(!path.isEmpty()){
                parents.put(path.pop(),cur);
            }
            return cur;
        }

        public boolean isSameSet(V a, V b) {
            return findFather(nodes.get(a)) == findFather(nodes.get(b));
        }

        public void union(V a, V b) {
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                Node<V> small = big == aHead ? bHead : aHead;
                parents.put(small, big);
                sizeMap.put(big, aSetSize + bSetSize);
                sizeMap.remove(small);
            }
        }

        public int sets() {
            return sizeMap.size();
        }


    }

}
